起床時間：1000
今天居然抽到Hard

題目

給你一個陣列 lists，裡面有 k 條 已經排好序 的 鏈結串列（linked list）。
請你把這 k 條串列合併成一條新的排序串列，並回傳它的頭節點。
📌 例子：
輸入：
lists = [[1,2,4],[1,3,5],[3,6]]

合併後的排序結果：
1 → 1 → 2 → 3 → 3 → 4 → 5 → 6
輸出：
[1,1,2,3,3,4,5,6]

直覺思路

原本想說用兩個for迴圈可以取得所有的value -> O(N)+O(K)
要有序的丟進去一個list -> 查找插入要花費O(N)
也就是 把所有值取出 → 逐一「找插入位置」放進一個保持有序的容器 → 最後再把它轉回 linked list

盲點

找插入位置 + 實際插入不是 O(1)：
若容器是陣列（Python list），即使二分查插入點是 O(log N)，搬移元素插入仍是 O(N)，整體每次插入 O(N)。插 N 次 ⇒ 總 O(N^2)。
若容器是鏈結串列，插入本身 O(1)，但你要線性走訪找到插入點 O(N)，插 N 次 ⇒ 總 O(N^2)。
你提到「兩個 for 迴圈 O(N)+O(K)」只是在掃描所有節點 + 掃清單頭，但每次插入的成本被忽略了；真正主導的是插入的 O(N)，累積成 O(N^2)。

官方暴力解研讀

可以全部取出，再做排序。這樣就只要排序一輪nlgn

核心就三步：「攤平 → 排序 → 重建」。

思想拆解

攤平（flatten）
把 k 條已排序鏈表的所有節點值，通通取出放進一個陣列 nodes。
成本：走過每個節點一次 ⇒ O(N)。
一次性排序
對陣列 nodes 做整體排序。
成本：排序 N 個值 ⇒ O(N log N)（主導複雜度）。
重建鏈表
依排序後的值，逐一新建節點接在結果尾端。
成本：再走一次 ⇒ O(N)；空間多用 O(N) 存陣列與（通常）新節點。

為什麼這叫暴力？
完全忽略了「各子鏈表已排序」這個結構性，把問題退化成「把 N 個數丟給排序器」。
因此時間落在 O(N log N)，而不是最優的 O(N log k)（k ≪ N 時差很多）。

完美解太難了，還要看~